package 回溯;

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class Solution1 {

    private ArrayList<List<Integer>> res;
    private boolean[] used;

    public List<List<Integer>> permute(int[] nums) {

        res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0)
            return res;

        used = new boolean[nums.length];
        LinkedList<Integer> p = new LinkedList<Integer>();
        generatePermutation(nums, 0, p);
        return res;
    }
    // p中保存了一个有index-1个元素的排列。
    // 向这个排列的末尾添加第index个元素, 获得一个有index个元素的排列
    private void generatePermutation(int[] nums, int index, LinkedList<Integer> p){
        System.out.println("现在进入的是：" +index + " : 得到" + p);
        if(index == nums.length){
            System.out.println(p);
            res.add(new LinkedList<>(p));
            System.out.println("get " + p + " , return");
            return;
        }
        for(int i = 0 ; i < nums.length ; i ++){
            if(!used[i]){
                System.out.println("index : "+index+"层准备添加："+ " p : " + p +
                        " , use " + nums[i]);
                used[i] = true;
                p.addLast(nums[i]);
                System.out.println("index : "+index+"层添加完毕准备下一层："+ " p : " + p );
                generatePermutation(nums, index + 1, p );
                System.out.println("index : "+index+"层结束"+(index+1)+"层递归" +" p : " + p );
                p.removeLast();
                used[i] = false;
                System.out.println("index : "+index+ "层恢复" +" p : " + p);
            }else {
                System.out.println("index : "+index+ "层用过了"+ nums[i]);
            }
        }
        System.out.println(index+"层结束"+" 返回上一层");
        return;
    }

    private static void printList(List<Integer> list){
        for(Integer e: list)
            System.out.print(e + " ");
        System.out.println();
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 3};
        List<List<Integer>> res = (new Solution1()).permute(nums);
        for(List<Integer> list: res)
            printList(list);

    }
}
